A packet-processing device, like a switch microchip, usually needs to buffer the packets into a packet memory (PM) having one or more banks while the device processes them. The current solution to store the packet in the device's packet memory is to assign multiple chunks (called pages) of packet memory to each packet, rather than a single big chunk. With this scheme, the packet is not stored consecutively in the banks of the packet memory, but rather scattered in one or more pages that together form a link list of pages that map throughout multiple banks of the packet memory. Further, a plurality of these banks (and the pages that map to them) are able to be logically grouped into pools (of banks and the associated pages). Therefore, the linked list of all the pages that a particular packet uses in the packet buffer needs to be maintained in the switch (in the buffer manager or BM); this linked list is traversed when the packet is read out of the packet buffer for transmission. Each page has associated a state that contains some information about the page. The state of all the pages in the packet processor device is maintained in the switch. A packet has associated a descriptor or token that among other fields contains the pointer to the first page. With this initial pointer, all the pages used by the packet can be retrieved in the same order they were used to store the incoming packet by traversing the link list built with the next-page pointers of the different page states. As a result, a linked list of all the pages (and therefore banks) that a particular packet uses is maintained in the switch and is then traversed to locate and read out the packet from the packet memory for transmission.
In these page based packet processing devices there is a tradeoff between the amount of wasted packet memory and the bandwidth demands placed on the buffer manager. The larger the size of each of the pages the fewer accesses needed to read and write the packet data and therefore the less stress on the bandwidth of the buffer manager. However, the larger the size of the pages means a larger portion of the packet memory is likely to be wasted or unused because a packet that does not fill an entire page will result in the remainder of the page being unused. On the other hand, the smaller the page size the lower the average wasted or unused packet memory, but the greater stress that is applied to the buffer manager due to the increase in the number of accesses required to read and write each packet to the smaller pages.
Additionally, in some packet processing devices if a portion of two or more packets have matching portions of packet data (e.g. header portions or body portions), those packets are able to share a page or pages storing the matching portions of the packet data so that the matching data is not stored twice in different locations (e.g. different pages). To keep track of the number of packets that need to use a page, the buffer manager maintains a reference count value for each of the pages that indicates the number of pages that share the page and have not yet read the packet data out from the page. For example, as the device determines that more packets need to use a page (e.g. more packets have portions that match the portion of data stored on the page), the device is able to increment the reference count value to account for the added packets that need to use the page. Similarly, as the data is read from the pages for one or more of the packets (such that the page no longer needs to be used for those packets), the device is able to decrement the reference count value to account for the less amount of packets that need to use the pages. Accordingly, when the reference count is decreased to zero, the device is able to recycle the page for reuse with other data because no more packets need to use the data stored on the page.